package union_find_Algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 1. 问题描述
 *      给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，
 *      其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
 *      你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
 *      返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
 *
 * 2. 算法分析
 *      并查集
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 交换字符串中的元素 {
    class UnionFind{
        int[] root;
        int maxsize;
        int[] rank;

        public UnionFind(int n) {
            maxsize = n;
            root = new int[n];
            rank = new int[n];
            for(int i = 0; i < n; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int x) {
            if(root[x] != x) {
                return find(root[x]);
            }
            return x;
        }

        public void union(int x,int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) {
                if(rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                }
                else if(rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                }
                else if(rank[rootX] == rank[rootY]) {
                    root[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
    }


    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();
        List list = new ArrayList();
        list.size();
    }

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int len = s.length();
        if(len == 0) {
            return s;
        }
        UnionFind uf = new UnionFind(len);
        // 1. 初始化uf
        for(List<Integer> pair : pairs) {
            int index1 = pair.get(0);
            int index2 = pair.get(1);
            uf.union(index1,index2);
        }

        // 2. 构建hash
        char[] charArray = s.toCharArray();
        HashMap<Integer,PriorityQueue<Character>> map = new HashMap<>(len);
        for(int i = 0; i < len; i++) {
            int root = uf.find(i); // 找到当前元素的root节点
            if(map.containsKey(root)) {
                // 如果已经存在，将第i个字符放进对应的优先队列中
                map.get(root).offer(charArray[i]);
            } else {
                // 不存在
                PriorityQueue<Character> PriorityQueue = new PriorityQueue<>();
                PriorityQueue.offer(charArray[i]);
                map.put(root,PriorityQueue);
            }
        }

        // 3. 拼接最终的结果
        // 由于上述采用的优先队列，所以每次取出的元素是字典序最小的(所在连通子图中的字符)
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < len; i++) {
            int root = uf.find(i);
            res.append(map.get(root).poll());
        }

        return res.toString();
    }




}
